package mid.class1;

/**
 * https://leetcode.cn/problems/longest-happy-prefix/
 * 最长快乐前缀
 */
public class Code03_LongestPrefix {

    public static void main(String[] args) {
        String str ="ababab";
        String s = longestPrefix(str);
        System.out.println("s = " + s);
    }

    public static String longestPrefix(String s) {
        return nextArray(s.toCharArray());
    }

    public static String nextArray(char[] arr) {
        // 构建的数组，arr+1，用于寸最长前缀
        int[] next = new int[arr.length + 1];
        int max = 0;
        next[0] = -1;
        next[1] = 0;
        int index = 2, cn = 0;
        while (index < arr.length + 1) {
            if (arr[cn] == arr[index - 1]) {
                next[index++] = ++cn;
                max = Math.max(max, cn);
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[index++] = 0;
            }
        }
        return new String(arr, 0, next[next.length - 1]);

    }
}
